/*
 * Graph.cpp
 *
 *  Created on: 16/ott/2014
 *      Author: angelo
 */


#include "Graph.h"

int Graph::nextId = 1;

Graph::Graph() {

	id = nextId++;
	width = 0;

	sumwidth = 0;

	active = true;

	vicini.clear();

	nextGraph = this;
	previousGraph = this;
}

Graph::Graph(int val) {

	id = nextId++;
	width = val;
	sumwidth = val;

	active = true;

	vicini.clear();

	nextGraph = this;
	previousGraph = this;
}

Graph::~Graph() {}

int Graph::getRandomWidth(int minVal, int maxVal, double percZero) {
	int ris = 0;

	double zeroRand = (double)rand() / RAND_MAX;

	if(zeroRand > percZero) {
		ris = (rand() % abs((maxVal - minVal))) + minVal;
	}

	return ris;
}

Graph::Graph(int minVal, int maxVal, int grado, int nNodes, double percZero) {

	int remainingnodes = nNodes;

	id = nextId++;
	width = getRandomWidth(minVal, maxVal, percZero);
	sumwidth = width;

	active = true;

	vicini.clear();

	nextGraph = this;
	previousGraph = this;

	// start iteration
	list<Graph*> listG;
	listG.push_back(this);

	remainingnodes--;

	while ((!listG.empty()) && (remainingnodes > 0)) {
		Graph* nextNode = listG.front();
		listG.pop_front();

		int nChild = (rand() % (grado - 1)) + 1;

		if (nChild > remainingnodes) {
			nChild = remainingnodes;
		}

		for (int i = 0; i < nChild; i++) {
			int newW = getRandomWidth(minVal, maxVal, percZero);
			Graph* newChild = new Graph(newW);

			nextNode->vicini.push_back(newChild);
			newChild->vicini.push_back(nextNode);

			listG.push_back(newChild);

			remainingnodes--;

			//aggiungo alla catena
			newChild->nextGraph = nextNode->nextGraph;
			newChild->previousGraph = nextNode;
			nextNode->nextGraph = newChild;
			if (nextNode->previousGraph == nextNode) {
				nextNode->previousGraph = newChild;
			}
			/*newChild->nextGraph = this->nextGraph;
			newChild->previousGraph = this;
			this->nextGraph = newChild;
			if (this->previousGraph == this) {
				this->previousGraph = newChild;
			}*/
		}
	}

	checkNonZeroLeaf(this);

	Graph *nxt = this;
	double tmpsumwidth = 0;
	do {
		tmpsumwidth += nxt->width;
		nxt = nxt->nextGraph;
	}while (nxt != this);

	nxt = this;
	do {
		nxt->sumwidth = tmpsumwidth;
		nxt = nxt->nextGraph;
	}while (nxt != this);


}

void Graph::checkNonZeroLeaf(Graph *parent) {
	list<Graph *>::iterator it;

	if ((vicini.size() == 1) && (width == 0)) {
		width = (rand() % 10) + 1;
	}

	for (it = vicini.begin(); it != vicini.end(); it++) {
		Graph *nestVicino = *it;

		if(nestVicino != parent) {
			nestVicino->checkNonZeroLeaf(this);
		}
	}
}

void Graph::printOut(Graph *parent) {
	list<Graph *>::iterator it;

	cout << id << ":" << width << ":" << sumwidth << " - ";

	for (it = vicini.begin(); it != vicini.end(); it++) {
		Graph *nestVicino = *it;
		cout << nestVicino->id << ":" << nestVicino->width << " ";
	}

	cout << endl;

	for (it = vicini.begin(); it != vicini.end(); it++) {
		Graph *nestVicino = *it;

		if(nestVicino != parent) {
			nestVicino->printOut(this);
		}
	}
}

void Graph::recursivePrintOut(void) {

	Graph *nxt = this;
	cout << "Recursive print: ";
	do {
		cout << nxt->id << ":" << nxt->width << ":" << nxt->sumwidth << " - ";
		nxt = nxt->nextGraph;
	}while (nxt != this);
	cout << endl;

}

void Graph::reactivateAllNodes(void) {
	Graph *nxt = this;
	do {
		nxt->active = true;
		nxt = nxt->nextGraph;
	}while (nxt != this);
}

int Graph::getBestSubGraph(int nMaxNode) {
	int ris = 0;

	Graph *nxt = this;
	do {
		int localSum = 0;
		int totSum = 0;

		list<Graph *> boundary;
		boundary.push_back(nxt);

		reactivateAllNodes();

		findBestSubTree(boundary, nMaxNode, localSum, totSum);

		if (totSum > ris) {
			ris = totSum;
		}

		nxt = nxt->nextGraph;
	}while (nxt != this);

	return ris;
}

void Graph::findBestSubTree(list<Graph *> boundary, int nMaxNode, int &localSum, int &totSum) {

	list<Graph *>::iterator it_border;

	if (nMaxNode == 0) {
		if (localSum > totSum) {
			totSum = localSum;
		}
		return;
	}

	for (it_border = boundary.begin(); it_border != boundary.end(); it_border++) {
		list<Graph *> newboundary;

		Graph *g = *it_border;

		localSum += g->width;
		g->active = false;

		for (list<Graph *>::iterator it_dup = boundary.begin(); it_dup != boundary.end(); it_dup++) {
			if (*it_dup != g) {
				newboundary.push_back(*it_dup);
			}
		}

		for (list<Graph *>::iterator it_b = g->vicini.begin(); it_b != g->vicini.end(); it_b++) {
			if((*it_b)->active) {
				newboundary.push_back(*it_b);
			}
		}

		findBestSubTree(newboundary, nMaxNode - 1, localSum, totSum);

		newboundary.clear();
		g->active = true;
		localSum -= g->width;
	}
}
